The encryption systems to which the invention relates make use of a fixed length secret "key", a message, and an encryption algorithm for computing a combination of the two called ciphertext with the property that someone knowing the secret key can efficiently compute the message from the ciphertext but someone not knowing the key cannot. The method used similar to that known in the literature as a "one-time pad". With a one-time pad, the "key" is not fixed length, but rather is a randomly chosen bit stream of the same size as the message and --as its name suggests--each key is only used once.
These systems are particularly applicable to messages in which the symbols are expressed in binary form. The key pad is then expressed as a bit stream and encryption is accomplished by applying a simple mathematical or logic function to the key pad and the message. A simple function to employ is the exclusive-OR. However, other functions, such as binary addition of the bit streams, may also be used. The message is recovered at the receiving end by reversing the encryption procedure, i.e. by applying to the key pad and the incoming ciphertext the inverse of the function used to encrypt the message. In the case of exclusive-OR encryption the message is recovered by passing the latter bit streams through an exclusive-OR circuit.
Since it is inconvenient to generate and securely deliver to sender and recipient large quantities of random bit streams, alternative designs use cryptographic pseudo-random number generators that are seeded with a fixed length secret known to both sender and recipient and produce identical bit streams for the sender and recipient but are not predictable by someone who does not know the fixed length secret. The most commonly known technique for doing this is called "Output Feedback Mode" (OFB). A related technique is called "Cipher Feedback Mode" (CFB"), in which the pseudo random stream is determined by the message itself as well as the fixed length secret. Both of these techniques are understood in the context of a reversible encryption algorithm like the "Data Encryption Standard" (DES). (See "Data Encryption Standard", Federal Information Processing Standards Publication No. 46, January 1977; "DES Modes of Operation", Federal Information Processing Standards Publication No. 81, December 1980)
Each of these arrangements has its advantages, depending on the requirements of users of the encryption system. In particular, OFB has the advantage of speed. Specifically, the key pad can be generated in advance of message transmission; encryption and decryption can therefore operate at the speed with which the input text and the key-pad bits can be combined, e.g., applied to a single exclusive-OR stage. That is, the speed of operation need not be limited by the speed with which the key-pad segments can be generated.
While the OFB has the advantages of a one-time key pad, it is susceptible to defeat by substitution of a bogus message. That is, if an intruder has access to the plaintext message and intercepts the ciphered message, he can reverse the operation of combining them, thereby recovering the key pad and then use the key pad to encode a substitute message.
CFB prevents message substitution by using successive segments of the ciphertext in generating successive segments of the key pad. An intruder can still recover the key pad in the manner described above. However, since the key pad is message-dependent, a substitute message that is enciphered using that key pad will be undecipherable to a meaningful symbol stream by the intended recipient of the original message. The attempt at message substitution will thus be discovered. However, this arrangement will be somewhat slower in operation than the first embodiment, since the key pad cannot be computed in advance of message origination.